package medium;

import javafx.util.Pair;

import java.util.HashSet;
import java.util.Set;
import java.util.Stack;

/**
 * @author cmqzyd0700@163.com
 * @version 1.0
 * @since 2021/10/11 19:50
 */
public class No45_跳跃游戏II {
    public static void main(String[] args) {
        Solution44 solution44 = new Solution44();
        //int[] nums = new int[]{2, 3, 4, 2, 0, 3, 0, 7};
        int[] nums = new int[]{0};
        int jump = solution44.jump(nums);
        System.out.println(jump);
    }
}

class Solution44 {
    public int jump(int[] nums) {
        //迭代,时间复杂度O(n)
        //当前所在位置
        int green = 0;
        //当前所在位置下跳跃的范围起
        int y1 = 0;
        //当前所在位置下跳跃的范围终
        int y2 = 0;
        //当前所在位置跳跃范围的最远跳跃距离
        int red = 0;
        int res = 0;
        //nums:{8}
        while (true) {
            y1 = green + 1;
            y2 = nums[green] + green;
            //如果到终点或者超出则次数++,同时退出循环
            if (y2 >= nums.length - 1) {
                res++;
                break;
            }
            //寻找范围内最远的距离
            for (int i = y1; i <= y2; i++) {
                if (nums[i] + i > red) {
                    red = nums[i] + i;
                    //为获取最远,只要远,则赋值
                    green = i;
                }
            }
            //次数+1
            res++;
        }
        //以上代码会在nums长度为1的时候多计算一位,因此:
        return nums.length == 1 ? res - 1 : res;
    }
}



    //public int jump(int[] nums) {
    //    //迭代
    //    //定义red:为从next要跳的位置
    //    int red = nums.length - 1;
    //    int tiao = 0;
    //    //定义next:为跳到red位置的最小索引(最小!!)
    //    int next = red;
    //    //多轮
    //    while (next > 0) {
    //        for (int i = 0; i <= next; i++) {
    //            if (nums[i] + i >= red) {
    //                //是否能跳到? 说明能
    //                next = i;
    //                break;
    //            }
    //        }
    //        red = next;
    //        //已经跳完,故跳跃次数+1
    //        tiao++;
    //    }
    //    return tiao;
    //}



    //public int jump(int[] nums) {
    //    if (nums.length == 1) {
    //        return 0;
    //    }
    //    //动态规划
    //    //dp[n]为到n位置(索引)的最小跳跃次数
    //    int[] dp = new int[nums.length];
    //    dp[0] = 0;
    //    dp[1] = 1;
    //    
    //    //外层循环计算dp[n]
    //    for (int i = 2; i <= nums.length - 1; i++) {
    //        //计算dp[4] 0-4
    //        for (int j = 0; j <= i; j++) {
    //            //判断是否能从dp[n](即索引为n)位置跳跃到当前i位置
    //            //当前dp[n]从dp[j]判断,如果j位置能跳到i位置,则获取dp[j]
    //            if (nums[j] + j >= i) {
    //                dp[i] = dp[j] + 1;
    //                break;
    //            }
    //        }
    //    }
    //    return dp[nums.length - 1];
    //}



    //public int jump(int[] nums) {
    //    //强行递归,暴力
    //    jump(nums, 0);
    //    return min;
    //}
    //
    ////全局深度,因为刚开始为0,适配
    //public int deep = -1;
    //public int min = Integer.MAX_VALUE;
    //
    ////curIndex:当前所在位置索引
    //public void jump(int[] nums, int curIndex) {
    //    deep++;
    //    
    //    //当前索引到底,记录深度,最小深度:min
    //    if (nums.length - 1 == curIndex) {
    //        min = Math.min(min, deep);
    //    }
    //    
    //    //0,不能继续
    //    if (nums[curIndex] == 0) {
    //        return;
    //    }
    //    
    //    //以4为例,curIndex=2,下一级:3-6
    //    int nextStart = curIndex + 1;
    //    if (nextStart >= nums.length) {
    //        return;
    //    }
    //    //理解:当前值+所在索引(当前值为跳跃次数)
    //    int nextEnd = nums[curIndex] + curIndex;
    //    //边界判断
    //    if (nextEnd >= nums.length) {
    //        nextEnd = nums.length - 1;
    //    }
    //    
    //    //疯狂递归
    //    for (int i = nextStart; i <= nextEnd; i++) {
    //        jump(nums, i);
    //        //回溯??
    //        deep--;
    //    }
    //}




